#include<cstdio>//uncle-lu
#include<cstring>
#include<algorithm>

int n, m, ans=0x7f7f7f7f;
int d[110][110];
int Map[110][110];
int x_turn[4]={1,-1,0,0};
int y_turn[4]={0,0,1,-1};

void DFS(int x, int y, bool flag, int sum)
{
	d[x][y] = sum;
	if(x==n && y==n)
	{
		ans = std::min(sum, ans);
		return ;
	}

	for(int i=0;i<4;++i)
	{
		int xx = x + x_turn[i], yy = y + y_turn[i];
		if(xx<1||xx>n||yy<1||yy>n)continue;

		if(Map[xx][yy]==-1)
		{
			if(flag)continue;
			Map[xx][yy] = Map[x][y];
			DFS(xx,yy,true,sum+2);
			Map[xx][yy] = -1;
		}
		else
		{
			if(Map[xx][yy]==Map[x][y])
				DFS(xx,yy,false,sum);
			else
				DFS(xx,yy,false,sum+1);
		}
	}

	return ;
}

int main()
{
	int a, b, c;
	scanf("%d%d",&n,&m);

	memset(d,0x7f7f7f7f,sizeof(d));
	memset(Map,-1,sizeof(Map));
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		Map[a][b] = c;
	}

	DFS(1,1,false,0);

	if(ans == 0x7f7f7f7f)
		printf("%d",-1);
	else
		printf("%d",ans);


	return 0;
}
